package leetcode.hot100;

class Solution62 {

    public static void main(String[] args) {
        System.out.println(uniquePaths1(7,4));
    }

    public static int uniquePaths(int m, int n) {
        //1,动态规划
        //dp[i][j]代表从[0][0]到[i][j]的路径条数
        //dp[i][j]=dp[i-1][j]+dp[i][j-1]
        // int[][] dp = new int[m][n];


        //2,其实数学方法直接算也可，就是相当于从m+n-2步选m-1步向下，n-1步向右，C(m+n-2,m-1)
        int fenzi = 1, fenmu = 1, i = n, j = 1;
        while(i<=m+n-2) fenzi *= i++;
        while(j<=m-1) fenmu *= j++;
        return fenzi/fenmu;
    }

    public static int uniquePaths1(int m, int n) {
        long ans = 1;
        for (int x = n, y = 1; y < m; ++x, ++y) {
            ans = ans * x / y;
        }
        return (int) ans;
    }
}
